package codeTop;

import java.util.Objects;

public class q297 {
    // Encodes a tree to a single string.
//    public String serialize(TreeNode root) {
//        if(root==null){
//            return "";
//        }
//        String mid = midOrder(root);
//        String left = leftOrder(root);
//        return mid+","+left;
//    }
//
//    private String leftOrder(TreeNode root) {
//        StringBuilder builder = new StringBuilder();
//        leftDfs(root,builder);
//        return builder.toString();
//    }
//
//    private void leftDfs(TreeNode root, StringBuilder builder) {
//        if (root == null) {
//            return;
//        }
//        leftDfs(root.left,builder);
//        builder.append(root.val);
//        leftDfs(root.right,builder);
//    }
//
//
//    private String midOrder(TreeNode root) {
//        StringBuilder builder = new StringBuilder();
//        midDfs(root,builder);
//        return builder.toString();
//    }
//
//    private void midDfs(TreeNode root, StringBuilder builder) {
//        if (root == null) {
//            return;
//        }
//        builder.append(root.val);
//        midDfs(root.left,builder);
//        midDfs(root.right,builder);
//    }
//
//    // Decodes your encoded data to tree.
//    public TreeNode deserialize(String data) {
//        if (data.length() <= 1) {
//            return null;
//        }
//        String[] split = data.split(",");
//        Map<Character,Integer> map = new HashMap<>();
//        for (int i = 0; i < split[1].length(); i++) {
//            map.put(split[1].charAt(i),i);
//        }
//        return build(split[0], split[1], 0, split[1].length() - 1,map);
//    }
//    int idx = 0;
//    public TreeNode build(String mid,String left,int l,int r,Map<Character,Integer> map){
//        if (l > r) {
//            return null;
//        }
//        TreeNode node = new TreeNode(mid.charAt(idx)-'0');
//        Integer i = map.get(mid.charAt(idx));
//        idx++;
//        node.left = build(mid,left,l,i-1,map);
//        node.right = build(mid,left,i+1,r,map);
//        return node;
//    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        dfs(root,sb);
        return sb.toString();
    }
    void dfs(TreeNode node, StringBuilder sb){
        if (node == null) {
            sb.append("none,");
            return;
        }
        sb.append(node.val);
        sb.append(",");
        dfs(node.left,sb);
        dfs(node.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (Objects.equals(data, "")) {
            return null;
        }
        String[] split = data.split(",");
        return build(split);
    }
    int idx = 0;
    private TreeNode build(String[] split) {
        if (split[idx].equals("none")){
            idx++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(split[idx++]));
        node.left = build(split);
        node.right = build(split);
        return node;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        q297 q = new q297();
        String serialize = q.serialize(root);
        q.deserialize(serialize);

    }
}
